% !TEX TS-program = pdflatex
\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{graphicx} 


\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large Lab 3 -- Solution\\ \vspace{0.2em}
        {\bf Search Algorithms}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstnameone \lastnameone\\
        \vspace{0.2em} \matriculationnumberone\\
        \vspace{0.2em} \firstnametwo \lastnametwo\\
        \vspace{0.2em} \matriculationnumbertwo
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstnameone}{Jiaqi	}
\newcommand{\lastnameone}{Weng}
\newcommand{\matriculationnumberone}{115131}

\newcommand{\firstnametwo}{Vasilii	}
\newcommand{\lastnametwo}{Ponteleev}
\newcommand{\matriculationnumbertwo}{115151}

\begin{document}
\pagestyle{plain}
\header


\textbf{Task 1}\\

a)\\
AND-OR graph is suited here, because the solution is a tree.\\
b)\\
define the matchstick's number like a list with a property of position, and calculate in this position i can win or lose the game.\\
for instances\\
let n=7, m=\{1,2,3\}\\
if i want to win the game, i need to go to the position 6, so it is the W position.\\
every action which can directly go to the 6 is the L position, like 3,4,5.\\
and the closest position which can not go to the 6 is also a W position, like 2.
and then action which can directly go to the 2 is the L position, like 0,1.\\
last, we can get the position list,\\
\begin{tabular}{c c c c c c c}
  0 & 1 & 2 &3 & 4 & 5 & 6 \\
  L & L & W & L & L & L & W\\
\end{tabular}
\\
the operation is opponent make a remove action, calculate the new W position and do the move.\\
control is move to the first W position in the first move,\\
so the parent node of the tree is \{startpos=0, endpos=2, move=2.\}\\
opponent does three kind of move, make three new child nodes\\
\{startpos=2, endpos=3, move=1.\},\{startpos=2, endpos=4, move=2.\},\{startpos=2, endpos=5, move=3.\}\\
so i need to move to the next W position 6 and win the game, like\\
\{startpos=3, endpos=6, move=3.\},\{startpos=4, endpos=6, move=2.\},\{startpos=5, endpos=6, move=1.\}\\
\\
c)\\
the leaf node of the solution is a subproblem of how can i go to the next W position from position i.position i is decided by the opponent's move choice.\\
\\
d)\\
when I get to the final W position, the node is solved.\\
e)\\
after calculate the position vector,\\
if the start position is W position, the player first move always loses the game, because after the first move he can never arrive at the next W position.\\
if the start position is L position, the player make the first move to the first W position, he can always win the game, because whatever the opponent move, he can always go to the next W position util win the game.\\
f)\\
see code nim.py\\

\textbf{Task 2}\\

Yes,  because every position of a queen is depends on the previous position of the other queens.\\


\textbf{Task 3}\\
(a) We can avoid expanding node several time by caching it, e.g. in a hash table, and checking new nodes against cache. This will not always be possible due memory limits. In case we're are running out of memory we can switch to more sophisticated cached schemes, such as LRU (Least Recently Used). 
\\Another aproach would be detecting the sutuation when the search space includes multiple paths to the same node and preventing one but all of them from being explored. 
\\(b) An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge). \\
For directed graph in addition to visited vertices we need to keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree.
\\(c) Suppose you can draw a route in the maze. If you're at a wall (or an area you've already plotted), return failure, else if you're at the finish, return success, else recursively try moving in the four directions. Plot a line when you try a new direction, and erase a line when you return failure, and a single solution will be marked out when you hit success. The method will always find a solution if one exists, but it won't necessarily be the shortest solution.  \\

\textbf{Task 4}\\
k, u  removed as dead ends, c - because it's not the part of a solution.\\

\textbf{Task 7}\\
a)
\\ $n_{opt}$ througout execution, only the result on each step. No exact order of result of successors(n) is specified and it doesn't matter.
\\ (1) $n_{opt}$ = s = 0
\\  (2) $n_{opt}$ = 3
\\  (3) $n_{opt}$ = 6
\\  (4) $n_{opt}$ = 8*
\\Outputs 8
\\\\b)
\\ $n_{opt}$ througout execution, only the result on each step. No exact order of result of successors(n) is specified and it doesn't matter.
\\ (1) $n_{opt}$ = s = 0
\\  (2) $n_{opt}$ = 3
\\  (3) $n_{opt}$ = 5
\\  (4) $n_{opt}$ = 6
\\Outputs FAIL 














\end{document}
